﻿/*  
  Copyright 2007-2009 The NGenerics Team
 (http://code.google.com/p/ngenerics/wiki/Team)

 This program is licensed under the GNU Lesser General Public License (LGPL).  You should 
 have received a copy of the license along with the source code.  If not, an online copy
 of the license can be found at http://www.gnu.org/copyleft/lesser.html.
*/

using System;
using System.Collections;
using System.Collections.Generic;

namespace NGenerics.DataStructures.Immutable
{

    /// <summary>
    /// An immutable stack, based on Eric Lippert's blog posting (http://blogs.msdn.com/ericlippert/archive/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack.aspx).
    /// </summary>
    public interface IStack<T>
        : IEnumerable<T>
    {
        /// <summary>
        /// Push a value onto the stack. This creates a new stack with the pushed item on top and all items of this stack underneath.
        /// </summary>
        /// <param name="value">The new item.</param>
        /// <returns>A new stack with this item on top.</returns>
        IStack<T> Push(T value);

        /// <summary>
        /// Returns a stack with the top-most item removed.
        /// </summary>
        /// <returns>A stack with the top-most item removed.</returns>
        /// <exception cref="InvalidOperationException">this exception is thrown when there is no item to remove.</exception>
        IStack<T> Pop();

        /// <summary>
        /// Returns the top-most item of this stack.
        /// </summary>
        /// <returns>The top-most item of this stack.</returns>
        /// <exception cref="InvalidOperationException">this exception is thrown when there is no item to return.</exception>
        T Peek();

        /// <summary>
        /// Gets a value indicating whether this stack is empty.
        /// </summary>
        bool IsEmpty { get; }
    }

    /// <summary>
    /// The implementation of the <see cref="IStack{T}"/> interface.
    /// </summary>
    /// <typeparam name="T">The type of items in this stack.</typeparam>
    /// <remarks>This implementation doesn't mutate the contents of a stack 
    /// but always returns a different instance with the proper state. This 
    /// allows efficient re-use of tails with the same contents and prevents 
    /// parallel threads to modify each other's stacks.</remarks>
    public sealed class ImmutableStack<T>
        : IStack<T>
    {
        /// <summary>
        /// A hidden stand-in for the empty stack.
        /// </summary>
        private sealed class EmptyStack
            : IStack<T>
        {
            public bool IsEmpty { get { return true; } }
            public T Peek() { throw new Exception("Empty stack"); }
            public IStack<T> Push(T value) { return new ImmutableStack<T>(value, this); }
            public IStack<T> Pop() { throw new Exception("Empty stack"); }
            public IEnumerator<T> GetEnumerator() { yield break; }
            IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
        }

        /// <summary>
        /// Private backing store for the <see cref="Empty"/> property.
        /// </summary>
        private static readonly EmptyStack empty = new EmptyStack();

        /// <summary>
        /// An empty stack.
        /// </summary>
        public static IStack<T> Empty { get { return empty; } }

        private readonly T head;
    
        private readonly IStack<T> tail;
        
        private ImmutableStack(T head, IStack<T> tail)
        {
            this.head = head;
            this.tail = tail;
        }

        /// <summary>
        /// Gets a value indicating whether this stack is empty.
        /// </summary>
        public bool IsEmpty { get { return false; } }

        /// <summary>
        /// Returns the top-most item of this stack.
        /// </summary>
        /// <returns>The top-most item of this stack.</returns>
        /// <exception cref="InvalidOperationException">this exception is thrown when there is no item to return.</exception>
        public T Peek() { return head; }
        
        /// <summary>
        /// Returns a stack with the top-most item removed.
        /// </summary>
        /// <returns>A stack with the top-most item removed.</returns>
        /// <exception cref="InvalidOperationException">this exception is thrown when there is no item to remove.</exception>
        public IStack<T> Pop() { return tail; }

        /// <summary>
        /// Push a value onto the stack. This creates a new stack with the pushed item on top and all items of this stack underneath.
        /// </summary>
        /// <param name="value">The new item.</param>
        /// <returns>A new stack with this item on top.</returns>
        public IStack<T> Push(T value) { return new ImmutableStack<T>(value, this); }
        
        /// <summary>
        /// Returns an enumerator, iterating over all items in this stack.
        /// </summary>
        /// <returns>An enumerator over all items in this stack.</returns>
        public IEnumerator<T> GetEnumerator()
        {
            for (IStack<T> stack = this; !stack.IsEmpty; stack = stack.Pop())
                yield return stack.Peek();
        }

        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
    }
}
